package Linked;

import java.util.Iterator;

public class List implements Iterable<Integer>{
    private final Node sentry;

    static class Node {
        public int value;
        public Node next;

        public Node() {
        }

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value + "}";
        }
    }

    //外部类构造器，初始化哨兵节点
    public List() {
        sentry = new Node(-1,null);
    }

    //头插节点
    public void addFirst(int value) {
        this.sentry.next = new Node(value,this.sentry.next);
    }

    //尾插节点
    public void addLats(int value) {
        Node p = this.sentry;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(value,null);
    }

    //重写迭代器
    @Override
    public Iterator<Integer> iterator() {

        return new Iterator<Integer>() {
            Node p = sentry.next;

            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public Integer next() {
                int k = p.value;
                p = p.next;
                return k;
            }
        };
    }

    //查找链表中的中间的节点(快慢指针):假如为奇数，则需要找到中间的节点；
    // 假如是偶数，则需要找到中间的两个节点的后一个节点。
    public Node searchMidNode() {
        //判断是否为空链表
        if (this.sentry.next == null) {
            return null;
        }

        Node fast = this.sentry.next;
        Node slow = this.sentry.next;
        while (fast!= null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    //判断是否为回文链表
    public boolean isPalindromeList() {
        Node p = this.sentry.next;

        //需要先找到中间节点
        Node midNode = this.searchMidNode();
        //然后将中间节点往后的链表进行反转，反转可以用递归的方法。
        Node newMidNode = reverseRecursion(midNode);
        //接下来就要对旧节点的前半段链表进行循环遍历来比较了每一个节点的值是否相同了
        //当且仅当，当迭代到反转后的链表的最后一个为 null 时，结束循环
        while (newMidNode != null) {
            if (p.value != newMidNode.value) {
                return false;
            }
            p = p.next;
            newMidNode = newMidNode.next;
        }
        return true;

    }

    //用递归实现链表反转
    public Node reverseRecursion(Node p) {
        if (p.next == null) {
            return p;
        }

        Node last = reverseRecursion(p.next);
        p.next.next = p;
        p.next = null;
        return last;
    }


    //判断是否闭环，如果是返回，则返回换入口；如果不是，则返回 null
    public Node isLoop() {
        Node fast = this.sentry.next;
        Node slow = this.sentry.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;


            if (slow == fast) {
                slow = this.sentry.next;

                //特例：当链表成为一个大环的时候(头尾相连),则直接返回

                //再相遇即为换入口节点
                while (true) {
                    if (slow == fast) {
                        return slow;
                    }
                    slow = slow.next;
                    fast = fast.next;

                }
            }
        }
        //从循环出来的不是闭环
        return null;
    }

}
